//最长的斐波那契式子序列
class Solution {
    public:
        int lenLongestFibSubseq(vector<int>& arr) {
            //1维解决不了问题
            //dp[i][j]表示:以i位置以及j位置的元素为结尾的所有的子序列中
            int n = arr.size();
            unordered_map<int,int> hash;
            for(int i = 0; i < n; i++) hash[arr[i]] = i;
            int ret = 2;
            vector<vector<int>> dp(n,vector<int>(n,2));
            for(int j = 2; j < n; j++)
            {
                for(int i = 1; i < j; i++)
                {
                    int a = arr[j] - arr[i];
                    if(hash.count(a) && a < arr[i]) dp[i][j] = dp[hash[a]][i] + 1;
                    ret = max(ret,dp[i][j]);
                }
            }
    
            return ret < 3 ? 0 : ret;
        }
    };